#include <iostream>
#include <stdio.h>
#include <stdlib.h> 
using namespace std;


void paixu(int array[], int len)
{
	for (int j=1; j<len; j++)
	{
		int key = array[j];
		int i = j-1;
			cout <<"排序中（准备插入）["<<key<<"]: ";
	        for (int i = 0;i<len;i++){
		           if (key == array[i])
	    	printf("(%2d) ",array[i]);
	    	else 
		    printf("%2d ",array[i]);
           	}
	        cout << endl;
		while (i>=0 && array[i]>key)
		{
			array[i+1] = array[i];
			i--;
			cout <<"排序中（插入中）["<<key<<"]: ";
	        for (int j = 0;j<len;j++){
	        	if (j==i+1)
		           printf("^%2d ",array[j]);
		        else
		           printf("%2d ",array[j]);
           	}
	        cout << endl;
		}
		array[i+1] = key;
		cout <<"排序中（插入放回）["<<key<<"]: ";
	    for (int i = 0;i<len;i++){
	    	if (key == array[i])
	    	printf("(%2d) ",array[i]);
	    	else 
		    printf("%2d ",array[i]);
       	}
	     cout << endl;
	}
} 

void paixu2(int array[], int len)
{
	for (int j=1; j<len; j++)
	{
		int key = array[j];
		int i = j-1;
		while (i>=0 && array[i]>key)
		{
			array[i+1] = array[i];
			i--;
		}
		array[i+1] = key;
	}	 
}

int main(){
	int array[] = {85,47,55,44,34,66,87,99,41,10,1,9};
	int length = sizeof(array)/sizeof(array[0]);
	cout <<"排序前: ";
	for (int i = 0;i<length;i++){
		printf("%2d ",array[i]);
	}
	cout << endl;
	paixu(array,length);
    cout <<"排序后: ";
	for (int i = 0;i<length;i++){
		printf("%2d ",array[i]);
	}
//	system("pause");
	cout << endl;
}